package part.part006;


import java.util.Arrays;

public class Code01_FindNumber {
    Object object;
    // 对数器
    public static void main(String[] args) {
        // 数组长度
        int N = 100;
        // 数组范围: 1~2000
        int V = 1000;
        // 测试次数
        int testNum = 5000;
        for (int i = 0; i < testNum; i++) {
            // 获取一个随机数组
            int[] arr1 = getRandomArray(N, V);
            Arrays.sort(arr1);
            int num = (int) (Math.random() * V);
            if (findNumber(arr1, num)!=findNumberNormal(arr1, num)) {
                System.out.println("出错了");
            }
        }
    }
    // 正常搜索
    public static boolean findNumberNormal(int[] arr, int num) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == num) {
                return true;
            }
        }
        return false;
    }

    // 使用二分法查找
    public static boolean findNumber(int[] arr, int num) {
        int l = 0;
        int r = arr.length-1;
        // 1 3 6 8 11 66 77
        // 0 1 2 3 4  5  6
        while (l <= r) {
            // 11
            int m = (l+r)/2;
            if (arr[m]<num) {
                l = m+1;
            } else if (arr[m]>num) {
                r = m-1;
            } else {
                return true;
            }
        }
        return false;
    }

    private static int[] copyArr(int[] arr1) {
        int l = arr1.length;
        int[] arr = new int[l];
        for (int i = 0; i < l; i++) {
            arr[i] = arr1[i];
        }
        return arr;
    }

    private static int[] getRandomArray(int n, int v) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            // 随机数生成
            arr[i] = (int) (Math.random() * v) + 1;
        }
//        System.out.println("xxxxxx");
        return arr;
    }


}
